package com.hackerrank.challenges.insertionsortadvancedanalysis;

import java.util.Scanner;

public class Solution {
	private static class Node {
		private int v, c = 1, h = 1, nc = 1;
		private Node l, r;
		public Node(int v) {
			this.v = v;
		}
		private int balanceFactor() {
			return (l == null ? 0 : l.h) - (r == null ? 0 : r.h);
		}
		private void recalculateCount() {
			c = (l == null ? 0 : l.c) + (r == null ? 0 : r.c) + nc;
		}
		private void recalculateHeight() {
			h = Math.max((l == null ? 0 : l.h), (r == null ? 0 : r.h)) + 1;
		}
		private void recalculate() {
			recalculateCount();
			recalculateHeight();
		}
		public Node insert(Node n) {
			if(n.v > v) {
				if(r == null)
					r = n;
				else
					r = r.insert(n);
				recalculate();
				if (r != null && r.balanceFactor() > 1) {
					// this is the first step in the right-left case.
					Node tr = r, trl = r.l, C = trl.r;
					tr.l = C;
					if(tr != null)
						tr.recalculate();
					trl.r = tr;
					trl.recalculate();
					r = trl;
					recalculate();
				}
				// This brings us to the right-right case.
				if (balanceFactor() < - 1) {
					Node tr = r, B = tr.l;
					r = B;
					recalculate();
					tr.l = this;
					tr.recalculate();
					return tr;
				}
			} else if(n.v < v) {
				if(l == null)
					l = n;
				else
					l = l.insert(n);
				recalculate();
				if (l != null && l.balanceFactor() < -1) {
					// this is the first step in the left-right case.
					Node tl = l, tlr = l.r, B = tlr.l;
					tl.r = B;
					if(tl != null)
						tl.recalculate();
					tlr.l = tl;
					tlr.recalculate();
					l = tlr;
					recalculate();
				}
				// This brings us to the left-left case.
				if (balanceFactor() > 1) {
					Node tl = l, C = tl.r;
					l = C;
					recalculate();
					tl.r = this;
					tl.recalculate();
					return tl;
				}
			}
			else if(n.v == v) {
				nc++;
				recalculateCount();
			}
			return this;
		}
		public int greaterCount(Node cn) {
			if(cn.v > v)
				return r.greaterCount(cn);
			if(cn.v < v)
				return (r == null ? 0 : r.c) + nc + l.greaterCount(cn);
			return r == null ? 0 : r.c;
		}
		public String toString() {
			return "{" + l + ", " + v + ":" + nc + ":" + c + ", " + r + "}";
		}
	}
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int T = in.nextInt();
		for(int t = 0; t < T; t++) {
			int N = in.nextInt(), c = 0;
			if(N > 0) {
				Node node = new Node(in.nextInt());
				for(int n = 1; n < N; n++) {
					Node cn = new Node(in.nextInt());
					node = node.insert(cn);
					System.out.println(node);
					c += node.greaterCount(cn);
				}
			}
			System.out.println(c);
		}
	}
}
